#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2025/3/22
# @USER    : Shengji He
# @File    : FindLargestPalindromeDivisibleK.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
import sys

sys.set_int_max_str_digits(0)

"""
- Math
- String
- Dynamic Programming
- Greedy
- Number Theory
"""

class Solution:
    """
    [3260. Find the Largest Palindrome Divisible by K](https://leetcode.com/problems/find-the-largest-palindrome-divisible-by-k/description/)
    You are given two positive integers n and k.

    An integer x is called k-palindromic if:
        - x is a palindrome.
        - x is divisible by k.
    Return the largest integer having n digits (as a string) that is k-palindromic.

    Note that the integer must not have leading zeros.

    Example 1:
        Input: n = 3, k = 5
        Output: "595"

        Explanation:
        595 is the largest k-palindromic integer with 3 digits.

    Example 2:
        Input: n = 1, k = 4
        Output: "8"

        Explanation:
        4 and 8 are the only k-palindromic integers with 1 digit.

    Example 3:

        Input: n = 5, k = 6
        Output: "89898"

    Constraints:
        - 1 <= n <= 10^5
        - 1 <= k <= 9
    """

    def largestPalindrome(self, n: int, k: int) -> str:
        """Deprecated, too slow"""
        half = (n + 1) // 2
        low = 10 ** (half - 1) - 1
        high = 10 ** half - 1
        start = n % 2

        for i in range(high, low, -1):
            half_str = str(i)
            k_palindromic = half_str + half_str[::-1][start:]
            if int(k_palindromic) % k == 0:
                return k_palindromic
        return ''

    def largestPalindrome_custom(self, n: int, k: int) -> str:
        if k in [1, 3, 9]:
            return '9' * n
        elif k == 2:
            return '8' * n if n < 3 else '8' + '9' * (n - 2) + '8'
        elif k == 4:
            return '8' * n if n < 5 else '88' + '9' * (n - 4) + '88'
        elif k == 5:
            return '5' * n if n < 3 else '5' + '9' * (n - 2) + '5'
        elif k == 8:
            return '8' * n if n < 7 else '888' + '9' * (n - 6) + '888'
        elif k == 6:
            if n < 3:
                return '6' * n
            s = [8] * n
            for i in range(1, n - 1):
                s[i] = 9
            total = sum(s)
            rem = total % 3
            if rem == 0:
                return ''.join(map(str, s))
            # Need to adjust
            if n % 2 == 1:
                mid = n // 2
                s[mid] = 9 - rem
                return ''.join(map(str, s))
            else:
                idx = n // 2 - 1
                new_total = rem
                while new_total % 3 != 0:
                    if idx == (n // 2 - 1):
                        s[idx] -= 1
                        s[n - 1 - idx] -= 1
                        new_total -= 2
                        if s[idx] == 0:
                            idx -= 1
                    else:
                        while s[idx] == 0:
                            idx -= 1
                        for i in range(idx + 1, n - 1 - idx):
                            s[i] = 9

                        if idx == 0:
                            s[idx] -= 2
                            s[n - 1 - idx] -= 2
                            if s[idx] <= 0:
                                return ''
                        else:
                            s[idx] -= 1
                            s[n - 1 - idx] -= 1
                        new_total = sum(s) % 3
                        idx = n // 2 - 1
                return ''.join(map(str, s))
        elif k == 7:
            if n < 3:
                return '7' * n
            half = (n + 1) // 2
            low = 10 ** (half - 1) - 1
            high = 10 ** half - 1
            start = n % 2
            for i in range(high, low, -1):
                half_str = str(i)
                k_palindromic = half_str + half_str[::-1][start:]
                if int(k_palindromic) % k == 0:
                    return k_palindromic
        return ''

    def largestPalindrome_other(self, n: int, k: int) -> str:
        if k in [1, 3, 9]:
            return '9' * n
        elif k == 2:
            return '8' * n if n < 3 else '8' + '9' * (n - 2) + '8'
        elif k == 4:
            return '8' * n if n < 5 else '88' + '9' * (n - 4) + '88'
        elif k == 5:
            return '5' * n if n < 3 else '5' + '9' * (n - 2) + '5'
        elif k == 8:
            return '8' * n if n < 7 else '888' + '9' * (n - 6) + '888'
        elif k == 6:
            if n < 3:
                return '6' * n
            elif n % 2 == 1:
                half = n // 2 - 1
                return '8' + '9' * half + '8' + '9' * half + '8'
            else:
                half = n // 2 - 2
                return '8' + '9' * half + '77' + '9' * half + '8'
        elif k == 7:
            # Precomputed largest 7-palindromic numbers for remainders mod 12
            dic = {0: '', 1: '7', 2: '77', 3: '959', 4: '9779', 5: '99799', 6: '999999', 7: '9994999',
                   8: '99944999', 9: '999969999', 10: '9999449999', 11: '99999499999'}
            l, r = divmod(n, 12)
            return '999999' * l + dic[r] + '999999' * l
        return ''


if __name__ == '__main__':
    # n = 3
    # k = 5

    n = 4869
    k = 7

    S = Solution()
    # print(S.largestPalindrome(n, k))
    # print(S.largestPalindrome_custom(n, k))
    print(S.largestPalindrome_other(n, k))
    print('done')
